This invention refers to the field of data communication and is in particular directed to redundant coding for error correction and detection.
Low-density parity check codes (LDPC) are a class of linear block codes which provide a near capacity performance on a large collection of data transmission and storage channels while simultaneously admitting implementable decoders. LDPC codes were first proposed by Gallager in his 1960 doctor dissertation (R. Gallager: “Low-density parity check codes”, IRE transformation series pp 21-28, January 1962). From practical point of view, the most significant features of Gallager's work have been the introduction of iterative decoding algorithms for which he showed that, when applied to sparse parity check matrices, they are capable of achieving a significant fraction of the channel capacity with relatively low complexity. Furthermore in LDPC codes the number of computations per bit and per iteration is independent of the block length.
A parity check matrix H defines the LDPC code. To each parity check matrix H exists a corresponding bipartite Tanner graph having variable nodes (V) and check nodes (C). A check node C is connected to a variable node V when the element hij of the parity check matrix H is 1. The parity check matrix H comprises M rows and N columns. The number of columns N corresponds to the number N of codeword bits within one encoded codeword Y transmitted via a communication channel. The codeword transmitted via the communication channel comprises K information bits and M parity check bits. The number of rows within the parity check matrix H corresponds to the number M of parity check bits in the codeword. In the corresponding Tanner graph there are M=N−K check nodes C, one check node for each check equation, and N variable nodes, one for each codebit of the codeword.
FIG. 1 shows an example for a sparse parity check matrix H and the corresponding bipartite Tanner graph.
LDPC codes have the ability to achieve a significant fraction of the channel capacity at relatively low complexity using iterative message passing decoding algorithms. These algorithms are based on the Tanner graph representation of codes, where the decoding can be understood as message passing between variable nodes V and check nodes C in the Tanner graph as shown in FIG. 1. Since messages are sent along the edges of the Tanner graph and are processed locally at each node of the Tanner graph one tries to keep the graph as sparse as possible to facilitate the subsequent iterative processing. Sparseness means that the number of edges between the variable nodes V and check nodes C is comparatively low, i.e. the corresponding check matrix H comprises a small number of ones.
How low density parity check LDPC codes do work is best demonstrated with a simple example as shown in FIGS. 2, 3.
FIG. 2 shows a simple Tanner graph for an LDPC code having four variable nodes V1, V2, V3, V4 and two check or constraint nodes C1, C2. Accordingly the block length of the codeword N=4 and the number of parity checkbits M=2. Consequently the number of information bits k is N−M=2.
The code rate R which is defined as the ratio between the number k of information bits and the block length N (R=k/N) is in this example ½.
The parity check matrix H corresponding to the bipartite Tanner graph is shown in FIG. 2.
For the LDPC code there exists a generator matrix G such that:G·HT=Ø  (1)i.e. a product of the generator matrix G and the transposed corresponding parity check matrix HT is zero.
FIG. 3 shows two transceivers which are connected via the Additive White Gaussian Noise (AWGN) Channel. LDPC codes can be applied for any possible communication channel. During data transmission the communication channel corrupts the transmitted codeword so that a one become zero or vice versa. To diminish the bit error rate BER the transmitting transceiver comprises as shown in FIG. 3 an LDCP-encoder which multiplies an information bit vector i having K=2 information bits with the generator matrix G of the LDPC code. In the example of FIG. 2 the LDPC-encoder outputs an encoded bit vector b which is modulated by a modulator within the transceiver. In the given example the modulator transforms a low logical value zero of the coded bit vector b to a transmission bit X=1 and a logically high value of the encoded bit vector b is transformed to X=−1. The transmitting transceiver transmits the modulated codeword X via the communication channel to the receiving transceiver as shown in FIG. 3. In the given example the communication channel is a binary input AWGN channel with a single sided spectral noise density NØ=8.
The receiving transceiver receives a codeword Y from the communication channel having N values.
The codeword Y is formed by adding noise to the transmission vector X:Y=X+Noise  (2)
The received codeword Y is demodulated and log-likelihood ratios (LLR) of the received codeword bits are calculated. For a binary input AWGN channel the log-likelihood ratios LLR are calculated as following:
                              P          j                =                              ln            ⁢                                                  ⁢                          (                                                Pr                  ⁡                                      (                                                                                            y                          j                                                /                                                  x                          j                                                                    =                      1                                        )                                                                    Pr                  ⁡                                      (                                                                                            y                          j                                                /                                                  x                          j                                                                    =                                              -                        1                                                              )                                                              )                                =                                    4                              N                0                                      ⁢                          Y              j                                                          (        3        )            
FIG. 3 shows the log-likelihood ratios for N0=8, where each received codeword value is divided by two. The log-likelihood ratios LLR give an a-priori estimate that a received codeword bit has a predetermined value.
The estimates are forwarded to the LDPC decoder within the transceiver which performs the LDPC decoding process.
A conventional LDPC decoder employs a standard message passing schedule for decoding the LDPC code which is called a flooding schedule as described in F. R. Kschischang and B. J. Frey “Iterative decoding of compound codes by probability propagation in graphical models”, IEEE J. Select. Areas Commun., vol. 16. Pp. 219-230, 1998.
A schedule is an updating rule which indicates the order of passing the messages between the nodes of the Tanner graph. A conventional LDPC decoder according to the state of the art employs a message passing procedure such as a belief propagation algorithm BP based on a flooding schedule.
FIG. 4 shows a flowchart of a belief propagation BP procedure employing a flooding schedule according to the state of the art.
FIG. 5 shows a belief propagation BP decoding process using the standard flooding procedure as shown in FIG. 4 with the example of FIG. 3.
As can be seen in FIG. 4 the received codeword Y is demodulated and log-likelihood ratios LLR are calculated.
In an initialization step S1 the messages Rcv from the check nodes C to the variable nodes V are set to zero for all check nodes and for all variable nodes. Further the messages Qvc from the variable nodes to the check nodes within the Tanner graphs are initialized with the calculated a-priori estimates Pv or log-likelihood ratios.
Further as shown in FIG. 4 an iteration counter iter is set to zero.
In a step S2 the messages Rcv from the check nodes to the variable nodes QVC are updated. The calculation is performed by a check node processor as shown in FIG. 7.
The calculation performed by the check node processor can be described as follows:
                                                        S              =                                                ∑                                      v                    ∈                                          N                      ⁡                                              (                        c                        )                                                                                            ⁢                                  φ                  ⁡                                      (                                          Q                      vc                                        )                                                                                                                                          for                ⁢                                                                  ⁢                all                ⁢                                                                  ⁢                v                            ∈                                                N                  ⁡                                      (                    c                    )                                                  ⁢                                  :                                                                                                                        R                cv                new                            =                                                φ                                      -                    1                                                  ⁡                                  (                                      S                    -                                          φ                      ⁡                                              (                                                  Q                          vc                                                )                                                                              )                                                                                          wherein                                                                              φ                ⁡                                  (                  x                  )                                            =                              (                                                      sign                    ⁡                                          (                      x                      )                                                        ,                                                            -                      log                                        ⁢                                                                                  ⁢                                          tanh                      ⁡                                              (                                                                                                          x                                                                                2                                                )                                                                                            )                                                                                                                          φ                                      -                    1                                                  ⁡                                  (                  x                  )                                            =                                                                    (                                          -                      1                                        )                                    sign                                ⁢                                  (                                      -                                          log                      ⁡                                              [                                                  tanh                          ⁡                                                      (                                                          x                              2                                                        )                                                                          ]                                                                              )                                                                                                        wherein              ⁢                                                          ⁢              the              ⁢                                                          ⁢              sign              ⁢                                                          ⁢              function              ⁢                                                          ⁢              is              ⁢                                                          ⁢              defined              ⁢                                                          ⁢              as              ⁢                              :                                                                                                        sign                ⁡                                  (                  x                  )                                            =                              {                                                                            0                                                                                      x                        ≥                        0                                                                                                                        1                                                                                      x                        <                        0                                                                                            }                                                                        (        4        )            
In a step S3 the messages Qvc from the variable nodes V to the check nodes C are updated by a symbol node processor as shown in FIG. 8.
The updating of the symbol to check messages Qvc can be described as follows:
                                                                        Q                V                            =                                                P                  V                                +                                                      ∑                                          C                      ∈                                              N                        ⁡                                                  (                          v                          )                                                                                                      ⁢                                      R                    CV                                                                                                                                          for                ⁢                                                                  ⁢                all                ⁢                                                                  ⁢                C                            ∈                              N                ⁡                                  (                  v                  )                                                                                                                        Q                VC                            =                                                Q                  V                                -                                  R                  CV                                                                                        (        5        )            
FIG. 5 shows the calculated check to symbol messages Rcv and symbol to check messages Qvc after the first iteration step.
In a step S4 an estimate vector {circumflex over (b)} is calculated from Qv according to the definition of the sign function and a syndrome vector S is calculated by multiplying the parity check matrix H with the calculated estimate vector {circumflex over (b)}:{circumflex over (b)}=sign(Q)s=H·{circumflex over (b)}  (6)
In a step S5 the iteration counter iter is incremented.
In a step S6 it is checked whether the iteration counter has reached a predefined maximum iteration value, i.e. a threshold value or whether the syndrome vector S is zero. If the result of the check in step S6 is NO the procedure continues with the next iteration.
In contrast if the result of the check in step S6 is positive it is checked in step S7 whether the syndrome vector S is zero or not. If the syndrome vector S is not zero the iteration has been stopped because the maximum number of iterations has been reached which is interpreted as a decoding failure. Accordingly the LDPC decoder outputs a signal indicating the decoding failure. When it is realized that the syndrome vector S is zero the coding was performed successfully, i.e. the decoding process has converged. In this case the LDPC decoder outputs the last calculated estimated vector {circumflex over (b)} as the correct decoded codeword.
For the given example of FIG. 3 the LDPC decoder of the receiving transceiver outputs the estimate vector {circumflex over (b)}=(1010)T and indicates that the decoding was performed successfully. Note that the decoded estimate vector {circumflex over (b)} corresponds to the output of the LDPC encoder within the transmitting transceiver.
FIG. 6 shows a block diagram of a conventional LDPC decoder employing the belief propagation BP decoding algorithm and using the standard flooding schedule according to the state of the art.
The LDPC decoder according to the state of the art as shown in FIG. 6 receives via an input (IN) the calculated log-likelihood ratios LLRs from the demodulator and stores them temporarily in a RAM as initialization values.
This RAM is connected to several symbol node processors as shown in FIG. 8. The output of the symbol node processors is connected to a further RAM provided for the Qvc messages. The Qvc-random access memory is connected to a ROM in which for every check node C of the Tanner graph the corresponding edges are memorized. This ROM controls a switching unit on the output side of the Qvc-RAM. The output of the switching unit is connected to several check node processors as shown in FIG. 7 which update the check to symbol messages Rcv. The updated Rcv messages are stored in a further RAM as shown in FIG. 6. At the output side the Rcv-RAM is connected to a further switching unit which is controlled by a further ROM in which for every variable node V within the Tanner graph the corresponding edges are stored. The output to the switching unit is connected to the symbol node processors.
The check node processors perform the update of the check to symbol messages Rcv as described in connection with step S2 of the flowchart shown in FIG. 4. The updated check to symbol messages Rcv are stored temporarily in the Rcv-RAM as shown in FIG. 6.
The symbol node processors perform the update of the symbol to check messages Qvc as described in connection with step S3 of the flow chart shown in FIG. 4. The updated symbol to check messages Qvc are stored temporarily in the Qvc-RAM.
The conventional LDPC decoder as shown in FIG. 6 further comprises a RAM for the output Qv messages calculated by the symbol node processors.
A convergence testing block computes the estimate {circumflex over (b)} and calculates the syndrome vector S as described in connection with step S4 of the flow chart of FIG. 4. Further the convergence testing block performs the checks according to steps S5, S6, S7 and indicates whether the decoding was successful, i.e. the decoder converged. In case that the decoding was successful the last calculated estimate is output by the LDPC decoder.
The conventional LDPC decoder employing a flooding update schedule as shown in FIG. 6 has several disadvantages.
The number of iterations necessary until the decoding process has converged is comparatively high. Accordingly the decoding time of the conventional LDPC decoder with flooding schedule is high. When the number of decoding iterations defined by the threshold value is limited the performance of the LDPC decoder according to the state of the art is degraded.
A further disadvantage of the conventional LDPC decoding method and the corresponding LDPC decoder as shown in FIG. 6 is that checking whether the decoding has converged is complicated and it is necessary to provide a separate converging testing block for processing a convergence testing. The convergence testing block of a conventional LDPC decoder as shown in FIG. 6 calculates a syndrome vector S by multiplying the parity check matrix H with the estimate vector {circumflex over (b)}.
Another disadvantage of the conventional LDPC decoding method employing a flooding schedule and the corresponding LDPC decoder as shown in FIG. 6 resides in that the necessary memory size is high. The LDPC decoder as shown in FIG. 6 comprises four random access memories (RAM), i.e. the RAM for the input Pv messages, a RAM for the output Qv messages, a further RAM for the Qvc messages and finally a RAM for the Rcv messages. Furthermore the LDPC decoder includes two read only memories (ROM) for storing the structure of the Tanner graph.
Accordingly it is the object of the present invention to provide a method for decoding a low density parity check codeword and a corresponding LDPC decoder overcoming the above mentioned disadvantages, in particular providing a decoding method which needs a small number of iterations for decoding a received codeword.